Regular tree grammar

In Computer Science, a regular tree grammar (RTG)^[1] is a formal grammar that describes a set of directed trees.

1 Definition
2 Derivation of Trees
3 Relation to other formal languages
4 See also
5 References
6 External links

Definition

A regular tree grammar $G$ is defined by the tuple

$G = (N, \Sigma, Z, P)$ ,

where

$N$ is a set of nonterminals,
$\Sigma$ is a ranked alphabet (i.e., an alphabet whose symbols have an associated arity) disjoint from $N$ ,
$Z$ is the starting nonterminal, with $Z \in N$ , and
$P$ is a set of productions of the form $A \rightarrow t$ , where $A \in N$ , and $t \in T_\Sigma(N)$ , where $T_\Sigma(N)$ is the associated term algebra.

Derivation of Trees

The grammar $G$ implicitly defines a set of trees: any tree that can be derived from $Z$ using the rule set $P$ is said to be described by $G$ . This set of trees is known as the language of $G$ . To express this more formally, we define the relation $\Rightarrow_G$ on the set $T_\Sigma (N)$ as follows:

For every $t_1, t_2 \in T_\Sigma (N), t_1 \Rightarrow_G t_2$ , if there is a context $S \in C$ and a production $A \rightarrow t \in P$ such that:

$t_1 = S[A]$ , and
$t_2 = S[t]$ .

The tree language generated by $G$ is the language

$L(G) = \{ t \in T_\Sigma | Z \Rightarrow_G^* t\}$ .

Where $\Rightarrow_G^*$ denotes successive applications of $\Rightarrow_G$ . Such languages are called Tree languages.

Relation to other formal languages

As shown by Rajeev Alur and Parthasarathy Madhusudan^[2]^[3] the class of regular tree languages coincides with nested words and visibly pushdown languages.

References

^ psu.edu - Regular tree grammars as a formalism for scope underspecification
^ Alur, R.; Madhusudan, P. (2004). Visibly pushdown languages. pp. 202. doi:10.1145/1007352.1007390. edit
^ Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words". Journal of the ACM 56 (3): 1–43. doi:10.1145/1516512.1516518. edit

External links

Tree Automata Techniques and Applications